package cn.edu.jxau.test;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * 基于拉链式hash的无序符号表
 * put：平均比较N/M次，其中N指键值对数量，M指链表数量
 * get：平均比较N/M次
 * 
 * @author 付大石
 */
public class SeparateChainingHashST<K, V> {

    public static void main(String[] args) {

        SeparateChainingHashST<Character, Integer> st = new SeparateChainingHashST(1);
        st.put('S', 0);
        st.put('E', 1);
        st.put('A', 2);
        st.put('R', 3);
        st.put('C', 4);
        st.put('H', 5);
        st.put('E', 6);
        st.put('X', 7);
        st.put('A', 8);
        st.put('M', 9);
        st.put('P', 10);
        st.put('L', 11);
        st.put('E', 12);
        st.put('F', 12);
        st.put('G', 12);
        st.put('H', 12);
        for (Character item : st.keys()) {
            System.out.println(item + "   " + st.get(item));
        }
        System.out.println(st.size());
    }

    /**
     * 初始拉链数
     */
    private static final int DEFAULT_CHAIN_NUM = 7;

    /**
     * 键值对数量
     */
    private int n;

    /**
     * chain的数量，与chains.length一致
     */
    private int m;

    /**
     * 基于无序链表的无序符号表，作为chain
     */
    private LinkedListST<K, V>[] chains;

    public SeparateChainingHashST() {
        this(DEFAULT_CHAIN_NUM);
    }

    public SeparateChainingHashST(int chainNum) {

        chains = (LinkedListST<K, V>[]) new LinkedListST[chainNum];
        m = chains.length;
    }

    private int hash(K key) {
        return (key.hashCode() & 0x7FFFFFFF) % m;
    }

    private LinkedListST<K, V> getChain(K key) {

        int hash = hash(key);
        if (chains[hash] == null) {
            chains[hash] = new LinkedListST<>();
        }
        return chains[hash];
    }

    public void put(K key, V value) {

        Objects.requireNonNull(key, "参数key不能为null");
        if (value == null) {
            delete(key);
            return;
        }
        if (n / m >= 10) {
            resize(m * 2);
        }
        if (!contains(key)) {
            n++;
        }
        getChain(key).put(key, value);
    }

    private void resize(int newChainNum) {

        System.out.println("resize to " + newChainNum);
        SeparateChainingHashST<K, V> tempST = new SeparateChainingHashST<>(newChainNum);
        for (K key : keys()) {
            tempST.put(key, get(key));
        }
        chains = tempST.chains;
        m = tempST.m;
    }

    public V get(K key) {

        Objects.requireNonNull(key, "参数key不能为null");
        return getChain(key).get(key);
    }

    public Iterable<K> keys() {

        List<K> list = new ArrayList<>();
        for (LinkedListST<K, V> chain : chains) {
            if (chain != null) {
                for (K key : chain.keys()) {
                    list.add(key);
                }
            }
        }
        return list;
    }

    public void delete(K key) {

        Objects.requireNonNull(key, "参数key不能为null");
        if (contains(key)) {
            n--;
        }
        getChain(key).delete(key);
        if (m > DEFAULT_CHAIN_NUM) {
            if (n / m < 2) {
                resize(m / 2);
            }
        }
    }

    public boolean contains(K key) {

        Objects.requireNonNull(key, "参数key不能为null");
        return get(key) != null;
    }

    public boolean isEmpty() {
        return n == 0;
    }

    public int size() {
        return n;
    }
}
